package m202405.d17;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/17 10:44
 */
public class Q5 {

    public static void main(String[] args) {
        Q5 q5 = new Q5();
        q5.longestPalindrome("ccc");
    }

    /**
     * dp[i][j] 表示从i到j是否是回文字串
     * <p>
     * dp[i][j] = dp[i+1][j-1] && s(i)==s(j)
     * <p>
     * dp[2][5] = dp[3][4] && s(2)==s(5)
     * dp[1][3] = dp[2][2] && s(1)==s(3)
     */
    public String longestPalindrome(String s) {
        int[] max = new int[2];
        boolean[][] dp = new boolean[s.length()][s.length()];
        //初始化，对于单个字母是true，两个字母相同则为true
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
            if (i < s.length() - 1) {
                dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
                test(max, dp[i][i + 1], i, i + 1);
            }
        }
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i + 2; j < s.length(); j++) {
                dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                test(max, dp[i][j], i, j);
            }
        }
        return s.substring(max[0], max[1] + 1);
    }

    private void test(int[] max, boolean flag, int s, int e) {
        if (flag && e - s + 1 > max[1] - max[0] + 1) {
            max[0] = s;
            max[1] = e;
        }
    }
}
